package algorithm.dp;
import java.util.*;
/**
 * @program: util
 * @description:
 * @author: zhouliangliang
 * @create: 2018-11-08 16:31
 * 动态规划上台阶问题
 * 一共10个台阶，每次只能上一个或者两个，求解一共有多少种上法
 * f(10) = f(9) + f(8)
 * 上第十个台阶的方法等于上第九个台阶的方法加上上第八个台阶的方法的总和
 **/
public class UpSteps {

    private Map<Integer, Integer> cache = new HashMap<Integer, Integer>();

    //递归算法
    public int upStep(int n) {
        if(n<1) return 0;
        if (n == 1) return 1;
        if(n == 2) return 2;

        return upStep(n-1) + upStep(n-2);
    }

    //改进的递归
    public int upStep2(int n) {
        if(n<1) return 0;
        if (n == 1) return 1;
        if(n == 2) return 2;

        if(cache.get(n) != null) {
            return cache.get(n);
        } else {
            int value = upStep(n-1) + upStep(n-2);
            cache.put(n, value);
            return value;
        }
    }

    //动态规划
    public int upStep3(int n) {
        int value = 0;
        int a = 1;
        int b = 2;
        for(int i=3; i<=n; i++) {
            value = a + b;
            a = b;
            b = value;
        }
        return value;
    }


    public static void main(String args[]) {
        System.out.println(new UpSteps().upStep(10));
        System.out.println(new UpSteps().upStep2(10));
        System.out.println(new UpSteps().upStep3(10));

    }

}
